package main.java.indi.zyj.classic150;

import main.java.indi.zyj.hot100.base.ListNode;

public class ReverseBetween {

    public ListNode reverseBetweenPlus(ListNode head, int left, int right) {

        if (left > right) return null;
        ListNode top = new ListNode(-1);
        top.next = head;
        ListNode preLeft = top;

        // 找到left的前一个节点
        for (int i = 0; i < left - 1 && preLeft != null; i++) {
            preLeft = preLeft.next;
        }

        ListNode cur = preLeft.next, next;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = preLeft.next;
            preLeft.next = next;
        }

        return top.next;
    }


    public ListNode reverseBetween(ListNode head, int left, int right) {

        if (left > right) return null;

        ListNode top = new ListNode(-1);
        top.next = head;
        ListNode preLeft = top, rightNode = top;

        // 找到left的前一个节点
        for (int i = 0; i < left - 1 && preLeft != null; i++) {
            preLeft = preLeft.next;
        }
        // 找到right节点
        for (int i = 0; i < right && rightNode != null; i++) {
            rightNode = rightNode.next;
        }

        // right的下一个节点以及left节点
        ListNode nextRight = rightNode.next;
        ListNode leftNode = preLeft.next;

        preLeft.next = null;
        rightNode.next = null;

        preLeft.next = reverseNode(leftNode);
        leftNode.next = nextRight;

        return top.next;

    }

    public ListNode reverseNode(ListNode head) {
        ListNode top = new ListNode(-1);
        ListNode p = head, q;
        while (p != null) {
            q = p.next;
            p.next = top.next;
            top.next = p;
            p = q;
        }
        return top.next;
    }

}
